package com.algorithm.trie;

import java.util.TreeMap;

/**
 * @Author: DOWN
 * @Date: 2022/5/9 17:11
 * @Comment: 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * <p>
 * 实现词典类 WordDictionary ：
 * <p>
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 * <p>
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // 返回 False
 * wordDictionary.search("bad"); // 返回 True
 * wordDictionary.search(".ad"); // 返回 True
 * wordDictionary.search("b.."); // 返回 True
 */
public class Solution211 {
    private class Node {
        /**
         * 是否为单词结尾
         */
        public boolean isWord;
        /**
         * 下一个节点
         */
        public TreeMap<Character, Node> next;

        /**
         * 初始化节点
         *
         * @param isWord 是否为单词结尾
         */
        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        /**
         * 默认不是单词结尾
         */
        public Node() {
            this(false);
        }
    }

    /**
     * 根节点
     */
    private Node root;
    /**
     * 长度
     */
    private int size;

    public Solution211() {
        root = new Node();
        size = 0;
    }

    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            //如果不存在，则新增节点
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        //判断当前是否为单词结尾
        if (!cur.isWord) {
            cur.isWord = true;
            //是，则长度加1
            size++;
        }
    }

    public boolean search(String word) {
        return search(root, word, 0);
    }

    /**
     * 查询方法-递归
     *
     * @param node  节点
     * @param word  单词
     * @param index 索引
     * @return boolean
     */
    public boolean search(Node node, String word, int index) {
        if (index == word.length()) {
            return node.isWord;
        }
        char c = word.charAt(index);
        //如果不包含点
        if (c != '.') {
            //如果不包含该节点
            if (node.next.get(c) == null) {
                return false;
            }
            return search(node.next.get(c), word, index+1);
        } else {
            //如果包含 点 ，则所有 Set中的下游字母都有可能是查询的单词
            for (char item : node.next.keySet()) {
                if (search(node.next.get(item), word, index+1)) {
                    return true;
                }
            }
            return false;
        }
    }
}
